package cn.corffen.test.algorithm.java;

import java.util.Arrays;
import java.util.List;

/**
 * 最强的学习能力是专注力
 */
public class DynamicProgramJava {


    public int climbStairs(int n) {
        if (n < 3) {
            return n;
        }
        int first = 1;
        int second = 2;
        int current = 0;
        for (int i = 3; i <= n; i++) {
            current = first + second;
            first = second;
            second = current;
        }
        return current;
    }

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int size = nums.length;
        int[] dp = new int[size + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= size; i++) {
            int current = dp[i - 2] + nums[i - 1];
            //动态转移方程是,第i个元素所能抢劫到的最大值.
            dp[i] = Math.max(current, dp[i - 1]);
        }

        return dp[size];
    }

    public int rob1(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int size = nums.length;
        if (size == 1) {
            return nums[0];
        }
        int first = 0;
        int second = 0;
        int current = 0;
        for (int i = 0; i < size; i++) {
            current = Math.max(second, first + nums[i]);
            first = second;
            second = current;
        }
        return current;
    }

    /**
     * 可以组成的等差数列的个数.
     * 动态规划就是在求解过程中,可以利用之前求过的解,有备忘功能
     * 比如[3,4,5,6]可以组成3个等差数列,以6为结尾的等差梳理的个数是2
     * 那么[3,4,5,6,7]就可以利用上一次的结果,那么以7为结尾的等差数列
     * 的个数是2(以6为结尾的个数)+1 = 3
     * <p>
     * 最后把每个以数组中元素为结尾的个数全部加起来,就是总共的个数.
     * 找到状态转移方程,要找到合适的dp定义
     *
     * @param A
     * @return
     */
    public int numberOfArithmeticSlices(int[] A) {
        if (A.length < 3) {
            return 0;
        }
        int[] dp = new int[A.length];
        int sum = 0;
        for (int i = 2; i < A.length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                sum += dp[i];
            }
        }
        return sum;
    }

    /**
     * 到达右下角,所经过的最短路径之和.
     * 想要到达dp[i][j] 的最短路径 必然是从上面或者左边 来到达.
     * 那么定义dp[i][j] 就是到达i,j时,需要的最短路径之和
     * 所以状态转移方程是 dp[i][j] = min(dp[i-1][j],dp[i][j-1])+a[i][j]
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 这里可以对空间进行压缩的
     * 用一维的空间来表示dp
     *
     * @param grid
     * @return
     */
    public int minPathSum2(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[j] = grid[i][j];
                } else if (i == 0) {
                    dp[j] = dp[j - 1] + grid[i][j];
                } else if (j == 0) {
                    dp[j] = dp[j] + grid[i][j];
                } else {
                    dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
                }
            }
        }
        return dp[n - 1];
    }


    public int[][] updateMatrix(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[][]{};
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    if (i > 0) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
                    }

                    if (j > 0) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                    }
                }
            }
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    if (i < m - 1) {
                        dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
                    }
                    if (j < n - 1) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
                    }
                }
            }
        }
        return dp;
    }

    /**
     * dp[i][j] 表示的是i,j位置的元素表示的正方形的边长
     * 状态转移方程是 左边,上面,左上中的值的最小者,然后+1
     *
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int maxSlide = 0;
        int[][] dp = new int[m][n];
        //遍历搜索
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    //边界条件
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        //记录上次的结果,并更新当前的结果
                        //状态转移方程
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                    }
                    maxSlide = Math.max(maxSlide, dp[i][j]);
                }
            }
        }
        return maxSlide * maxSlide;
    }

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

    public int numDecodings(String s) {
        int size = s.length();
        if (size == 0) {
            return 0;
        }
        int[] dp = new int[size];
        char[] chars = s.toCharArray();
        if (chars[0] == '0') {
            return 0;
        }
        dp[0] = 1;
        for (int i = 1; i < size; i++) {
            if (chars[i] != '0') {
                dp[i] = dp[i - 1];
            }
            int number = 10 * (chars[i - 1] - '0') + (chars[i] - '0');
            if (number >= 10 && number <= 26) {
                if (i == 1) {
                    dp[i]++;
                } else {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[size - 1];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int len = word.length();
                if (i >= len && s.substring(i - len, i).equals(word)) {
                    dp[i] = dp[i] || dp[i - len];
                }
            }
        }
        return dp[n];
    }

    /**
     * 最长子序列的问题,是定义以i为结尾的值,是最长子序列
     * 那么遍历完整个数组,在求最大值.就是索要的结果
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        if (length == 0) {
            return 0;
        }
        int[] dp = new int[length];
        Arrays.fill(dp, 1);
        int maxValues = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxValues = Math.max(maxValues, dp[i]);
        }
        return maxValues;
    }

    /**
     * 最长公共子序列
     * dp表示的是第一个字符串以i为结尾,第二个字符串以j结尾的最长公共子序列
     * 状态转移方程是,如果第i个和第j个相等,那么就将dp[i-1][j-1]的结果+1
     *
     * @param text1
     * @param text2
     * @return
     */
    int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }


    /**
     * 0-1背包问题
     * 定义dp为第i个物品体积不超过j的情况下的最大价值dp[i][j]
     * 状态转移方程:如果第i个物品添加到背包,那么最大值就是 dp[i-1][j-w]+v与dp[i-1][j]的较大值
     * 如果第i个物品不添加到背包,那么dp就是dp[i-1][j]
     *
     * @param W
     * @param N
     * @param weights
     * @param values
     * @return
     */
    public int knapsack(int W, int N, int[] weights, int[] values) {
        int[][] dp = new int[N + 1][W + 1];//表示第i件物品体积不超过j的情况下的最大价值
        for (int i = 1; i <= N; i++) {
            int w = weights[i - 1];
            int v = values[i - 1];
            for (int j = 1; j <= W; j++) {
                if (j >= w) {
                    //可以容纳当前物品时,取前一个物品装进背包时,并且空间是当前空间j-当前物品的容量
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
                } else {
                    //没有装进背包,就是前一个物品装进背包时的最大价值
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N][W];
    }

    /**
     * 对于上面的公式,可以对空间进行压缩
     * 因为dp[i][j]的值总是从dp[i-1][j]或者dp[i-1][j-w]中获取
     * 所以可以变为一维数组
     * dp的值,只跟背包的容量有关
     * 内循环调用时,才可以调用dp[j-w]的值
     * 背包的空间j需要大于当前物品的容量w才可以
     * 也就是说如果背包的容量固定,那么能取到的最大值也就固定
     *
     * @return
     */
    public int knapsack2(int W, int N, int[] weights, int[] values) {
        int[] dp = new int[W + 1];
        for (int i = 1; i < N; i++) {
            int w = weights[i - 1];
            int v = values[i - 1];
            //0-1背包倒序取值,从最大容量W开始,一直到满足大于当前物品的容量开始
            for (int j = W; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
        return dp[W];
    }


    /**
     * 完全背包,一个物品可以拿多次
     * 与0-1背包问题是取出当前dp[i][j-w]而不是前一个物品的dp[i-1][j-w]
     * 其他的与0-1背包问题一模一样
     *
     * @param W
     * @param N
     * @param weights
     * @param values
     * @return
     */
    public int knapsack3(int W, int N, int[] weights, int[] values) {
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 1; i <= N; i++) {
            int w = weights[i - 1];
            int v = values[i - 1];
            for (int j = 1; j < W; j++) {
                if (j >= w) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w] + v);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N][W];
    }

    /**
     * 完全背包的空间压缩
     * 内循环是正向遍历,从w开始
     * 而0-1是内循环逆序遍历
     *
     * @param W
     * @param N
     * @param weights
     * @param values
     * @return
     */
    public int knapsack4(int W, int N, int[] weights, int[] values) {
        int[] dp = new int[W + 1];
        for (int i = 1; i < N; i++) {
            int w = weights[i - 1];
            int v = values[i - 1];
            for (int j = w; j <= W; j++) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
        return dp[W];
    }


    /**
     * 本题本质上就是一个0-1背包问题
     * 从N个数中,挑选若干个数,使其值加起来满足target
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        int n = nums.length;
        //表示从数组的[0,i]这个子区间内挑选一些正整数,使得这些数的和恰好等于j
        boolean[][] dp = new boolean[n + 1][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++) {
            int w = nums[i - 1];//当前数量的值
            for (int j = w; j <= target; j++) {
                //dp[i-1][j-w]表示选择nums[i],并且在[0,i-1]这个区间的他们的和是[j-w]
                //此时有dp[i][j] = dp[i-1][j-w]
                //如果不选择nums[i],在[0,i-1]这个子区间,已经有一部分元素使得他们的和是j
                //此时有dp[i][j] = dp[i-1][j]
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - w];
            }
        }
        return dp[n][target];
    }

    /**
     * 空间压缩
     *
     * @param nums
     * @return
     */
    public boolean canPartition2(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        int n = nums.length;
        //表示从数组的[0,i]这个子区间内挑选一些正整数,使得这些数的和恰好等于j
        boolean[] dp = new boolean[target + 1];
        for (int i = 0; i < n; i++) {
            dp[0] = true;
        }
        for (int i = 1; i <= n; i++) {
            int w = nums[i - 1];//当前数量的值
            for (int j = target; j >= w; j--) {
                dp[j] = dp[j] || dp[j - w];
            }
        }
        return dp[target];
    }

    /**
     * 有多个容量的背包问题
     * <p>
     * dp[i][j]表示的是使用i个0和j个1,最多能拼出来的字符串数目
     * <p>
     * 如果可以把当前的字符串添加到背包,那么就有dp[i-count[0]][j-count[1]] 在加1
     * 不能添加的话,就还是dp[i][j]
     * 二者取其最大值
     * dp[i][j] = Math.max(dp[i][j],dp[i-count[0]][j-count[1]]+1)
     *
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int[] c = countZeroAndOne(str);
            for (int i = m; i >= c[0]; i--) {
                for (int j = n; j >= c[1]; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - c[0]][j - c[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    private int[] countZeroAndOne(String s) {
        int[] c = new int[2];
        for (int i = 0; i < s.length(); i++) {
            c[s.charAt(i) - '0']++;
        }
        return c;
    }

    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        //dp[i]表示的是凑够 i的金额,需要的硬币的数量
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 2);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    //这是完全背包的问题
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 2 ? -1 : dp[amount];
    }

    /**
     * 题目描述
     * 给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可
     * 以将两个字符串变成相同。
     * 输入输出样例
     * 输入是两个字符串，输出是一个整数，表示最少的步骤。
     * Input: word1 = "horse", word2 = "ros"
     * Output: 3
     * 在这个样例中，一种最优编辑方法是（1）horse -> rorse （2）rorse -> rose（3）rose -> ros。
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        //定义一个dp数组,表示第一个单词在第i个位置,第二个单词在第j个位置,需要编辑的次数
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    //当第i位和第j位的字符相等时,dp[i][j] = dp[i-1][j-1];不相等时是dp[i-1][j-1]+1
                    //插入i位置/删除j位置,dp[i][j] = dp[i][j-1]+1  比如 hors --> horse
                    //插入j位置/删除i位置,dp[i][j] = dp[i-1][j] +1 比如 rose --> ros
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1),
                            Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 给定一个A,将其变成n个A,最少需要几步.
     * 只使用复制和粘贴
     *
     * @param n
     * @return
     */
    public int minSteps(int n) {
        int[] dp = new int[n + 1];
        int h = (int) Math.sqrt(n);
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 2; j <= h; j++) {
                if (i % j == 0) {
                    dp[i] = dp[j] + dp[i / j];
                }
            }
        }
        return dp[n];
    }

    public int maxProfit(int[] prices) {
        int maxPro = 0;
        int profit;
        int historySize = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            historySize = Math.min(historySize, prices[i]);
            profit = prices[i] - historySize;
            maxPro = Math.max(maxPro, profit);
        }
        return maxPro;
    }

    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        //如果k大于总天数,那么一有收益就卖出,最终就是最大值
        if (k >= len) {
            return maxProfitUnlimited(prices);
        }
        //第k次 买入时的最大收益和卖出时的最大收益
        int[] buys = new int[k + 1];
        int[] sells = new int[k + 1];
        Arrays.fill(buys, Integer.MIN_VALUE);//初始值很重要
        for (int i = 0; i < prices[i]; i++) {
            for (int j = 1; j <= k; j++) {
                //第k次买入时的最大收益 为上一次卖出时的收益减去当天的价格
                buys[j] = Math.max(buys[j], sells[j - 1] - prices[i]);
                //第k次卖出时的最大收益是, 第k次买入时的收益+当天的价格
                sells[j] = Math.max(sells[j], buys[j] + prices[i]);
            }
        }
        //最大收益是第k次卖出时的收益
        return sells[k];
    }

    private int maxProfitUnlimited(int[] prices) {
        int maxPro = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxPro += prices[i] - prices[i - 1];
            }
        }
        return maxPro;
    }



    public static void main(String[] args) {
        DynamicProgramJava demo = new DynamicProgramJava();
        for (int i = 1; i <= 17; i++) {
            System.out.println("dp[" + i + "]:" + demo.numSquares(i));
        }
    }
}
